/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: 邹陆川
 * @Date: 2022/04/19/2:10 下午
 * @Description:归并排序：
 * 核心思想：使用了分治法和递归结合使用
 * 首先将他们按照对半分开，一直分到每个组只有一个元素
 * 其次将他们合并起来，原路合并，合并的时候将他们排好序，每次合并都是一次排序
 *
 * 时间复杂度为：O=(nlogN)
 */
public class Merge {
  public static void sort(Integer[] a,int low,int high){
    int mid = (low+high)/2;
    if(low<high){
      sort(a,low,mid);
      sort(a,mid+1,high);
      //左右归并
      merge(a,low,mid,high);
    }
  }

  public static void merge(Integer[] a, int low, int mid, int high) {
    int[] temp = new int[high-low+1];
    int i= low;
    int j = mid+1;
    int k=0;
    // 把较小的数先移到新数组中
    while(i<=mid && j<=high){
      if(a[i]<a[j]){
        temp[k++] = a[i++];
      }else{
        temp[k++] = a[j++];
      }
    }
    // 把左边剩余的数移入数组
    while(i<=mid){
      temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while(j<=high){
      temp[k++] = a[j++];
    }
    // 把新数组中的数覆盖nums数组
    for(int x=0;x<temp.length;x++){
      a[x+low] = temp[x];
    }
  }
}
